
/******************************************************************************************************
*******************************************************************************************************
**************************************                        *****************************************
**************************************     DECOMPRESSING      *****************************************
**************************************                        *****************************************
*******************************************************************************************************
******************************************************************************************************/

#include <stdio.h>
#define BITS 12                   
#define HASHING_SHIFT BITS-8     
#define MAX_VALUE (1 << BITS) - 1 
#define MAX_CODE MAX_VALUE - 1    
				  
#if BITS == 14
  #define TABLE_SIZE 18041        /* Setting the number of bits to 12, 13 or 14 */
#endif                            
#if BITS == 13                                         
  #define TABLE_SIZE 9029
#endif
#if BITS <= 12
  #define TABLE_SIZE 5021
#endif

void *malloc();

int *code_value;                  /* This is the code value array        */
unsigned int *prefix_code;        /* This array holds the prefix codes   */
unsigned char *append_character;  /* This array holds the appended chars */
unsigned char decode_stack[4000]; /* This array holds the decoded string */


/************************************************************************
**
** 
**           It then expands test.lzw into test.out.
**   Test.out should then be an exact duplicate of the input file.
** 
**
*************************************************************************/


main()
{
FILE *input_file;
FILE *output_file;
FILE *lzw_file;
char input_file_name[81];

         /****************************************************************************
                          The three buffers are needed for the compression phase.
         ******************************************************************************/

  code_value=malloc(TABLE_SIZE*sizeof(unsigned int));
  prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int));
  append_character=malloc(TABLE_SIZE*sizeof(unsigned char));
  if (code_value==NULL || prefix_code==NULL || append_character==NULL)
  {
    printf("Fatal error allocating table space!\n");
    exit();
  }


         /****************************************************************************
                           Now open the files for the expansion.
         ******************************************************************************/

    printf("Input file name? ");
    scanf("%s",input_file_name);

input_file=fopen(input_file_name,"rb");
lzw_file=fopen("test.lzw","rb");
  output_file=fopen("test.xxx","wb");
  if (lzw_file==NULL || output_file==NULL)
  {
    printf("Fatal error opening files.\n");
    exit();
  };
         /****************************************************************************
                                          Expand the file.
         ******************************************************************************/
  expand(lzw_file,output_file);
  fclose(lzw_file);
  fclose(output_file);

  free(prefix_code);
  free(append_character);
}

/************************************************************************
**
** 
**                     This is the expansion routine.   
**   
**      It takes an LZW format file, and expandsit to an output file.
**
*************************************************************************/

expand(FILE *input,FILE *output)
{
unsigned int next_code;
unsigned int new_code;
unsigned int old_code;
int character;
int counter;
unsigned char *string;
char *decode_string(unsigned char *buffer,unsigned int code);

  next_code=256;           /* This is the next available code to define */
  counter=0;               
  printf("Expanding...\n");

  old_code=input_code(input);  /* Read in the first code, initialize the */
  character=old_code;          /* character variable, and send the first */
  putc(old_code,output);       /* code to the output file                */


         /************************************************************************************
              This is the main expansion loop.  It reads in characters from the LZW file
             until it sees the special code used to inidicate the end of the data.                         
         ******************************************************************************/
 
while ((new_code=input_code(input)) != (MAX_VALUE))
  {
    if (++counter==1000)   /* This section of code prints out     */
    {                      /* an asterisk every 1000 characters   */
      counter=0;          
      printf("*");
    }


         /************************************************************************************
              This code checks for the special STRING+CHARACTER+STRING+CHARACTER+STRING
                  case which generates an undefined code.  It handles it by decoding
              the last code, and adding a single character to the end of the decode string.    
         ******************************************************************************/

if (new_code>=next_code)
    {
      *decode_stack=character;
      string=decode_string(decode_stack+1,old_code);
    }


         /************************************************************************************
                     Otherwise we do a straight decode of the new code.                         
         ******************************************************************************/
else
      string=decode_string(decode_stack,new_code);

   /************************************************************************************
                    Now we output the decoded string in reverse order.                     
         ******************************************************************************/
   character=*string;
    while (string >= decode_stack)
      putc(*string--,output);

   /************************************************************************************
                   Finally, if possible, add a new code to the string table.                  
         ******************************************************************************/
 if (next_code <= MAX_CODE)
    {
      prefix_code[next_code]=old_code;
      append_character[next_code]=character;
      next_code++;
    }
    old_code=new_code;
  }
  printf("\n** The test.xxx has created **\n");
  getch();
}


   /************************************************************************************
      This routine simply decodes a string from the string table, storingit in a buffer.
        The buffer can then be output in reverse order by the expansion program.             
         ******************************************************************************/

char *decode_string(unsigned char *buffer,unsigned int code)
{
int i;

  i=0;
  while (code > 255)
  {
    *buffer++ = append_character[code];
    code=prefix_code[code];
    if (i++>=4094)
    {
      printf("Fatal error during code expansion.\n");
      exit();
    }
  }
  *buffer=code;
  return(buffer);
}


   /************************************************************************************
                The following routine is used to output variable length codes.   
       ******************************************************************************/

input_code(FILE *input)
{
unsigned int return_value;
static int input_bit_count=0;
static unsigned long input_bit_buffer=0L;

  while (input_bit_count <= 24)
  {
    input_bit_buffer |= 
        (unsigned long) getc(input) << (24-input_bit_count);
    input_bit_count += 8;
  }
  return_value=input_bit_buffer >> (32-BITS);
  input_bit_buffer <<= BITS;
  input_bit_count -= BITS;
  return(return_value);
}
         
                               /************END**************/